import sys

class Solution(object):
    def maxProfit(self, prices):
        # use state machine
        if len(prices) == 0:
            return 0
        s0 = [0]
        s1 = [-prices[0]]
        s2 = [-sys.maxsize]
        for i in range(1, len(prices)):
            s0.append(max(s0[i-1], s2[i-1]))
            s1.append(max(s0[i-1]-prices[i], s1[i-1]))
            s2.append(s1[i-1]+prices[i])
        return max(s0[-1], s2[-1])
        